1. Field
The present invention generally relates to rendering two-dimension representations from three-dimensional scenes, and more particularly to accelerating ray tracing for such rendering.
2. Description of Related Art
Rendering photo-realistic images with ray tracing is known in the computer graphics arts to have the ability to produce photo-realistic images, including realistic shadow and lighting effects, because ray tracing models the physical behavior of light interacting with elements of a scene. However, ray tracing is also known to be computationally intensive, and at present, even a state of the art graphics workstation requires a substantial amount of time to render a complicated, high resolution scene using ray tracing.
Ray tracing usually involves obtaining a scene description composed of geometric primitives, such as triangles, that describe surfaces of structures in the scene. For example, a scene may comprise a car on a street with buildings on either side of the street. The car in such a scene may be defined by a large number of triangles (e.g., 1 million triangles) that approximate a continuous surface. A camera position from which the scene is viewed is defined. An image plane of a selected resolution (e.g., 1024×768 for an SVGA display) is disposed at a selected position between the camera and the scene.
A principal objective of ray tracing is to determine a color and intensity for each pixel of the image plane, such that this image can thereafter be displayed on a monitor, for example. In the physical world, viewing such a scene from the camera's perspective would result in light rays reaching the camera that owe their existence to one or more light sources, including diffuse and directed light sources. In the physical world, these light sources project light energy into the scene, and this light energy is transmitted, diffracted, reflected, and/or absorbed according to the types of materials that the light contacts, and the order in which they are contacted, during its journey from light source to the camera. This process is what ray tracing attempts to duplicate.
Although the physical world operates by light energy being traced from a source to the camera, only a small portion of the light generated by a source arrives at the camera. Therefore, it has been recognized that rays, for most circumstances, should be traced from the camera back to determine intersections with light sources.
A ray tracing algorithm mainly involves casting one or more rays from the camera through each pixel of the image into the scene. Each ray is then tested against each primitive composing the scene to identify a primitive which that ray intersects, then it is determined what effect that primitive has on the ray, for example reflecting and/or refracting it. Such reflection and/or refraction causes the ray to proceed in a different direction, and/or split into multiple secondary rays, which can take different paths. All of these secondary rays are then tested against the scene primitives to determine primitives they intersect, and the process recursively continues until the secondary (and tertiary, etc.) ray terminates by, for example, leaving the scene, or hitting a light source. While all of these ray/primitive intersections are being determined, a tree mapping them is created. After a ray terminates, the contribution of the light source is traced back through the tree to determine its effect on the pixel of the scene.
Once a primitive has been identified as being intersected by a ray, shading calculations are done to determine what effect the intersection has. These shading calculations are usually specified by shader code specific for a material assigned to the primitive intersected. Texture information can also be used during such shading calculations. The shader code specifies how the ray will interact with the primitive, such as whether the ray will be reflected or refracted, as well as whether additional rays will be spawned based on that intersection. These additional rays are for determining properties of the primitive intersected and as such the color of the primitive at the intersection point is not determined until these additional rays are resolved by additional ray tracing operations.
Thus, even though an intersection has been determined, without completing the additional ray tracing, which may in turn lead to additional shading for additional intersections, the color of the intersected primitive is not yet determined, which is why most ray tracers build a tree of intersections, and after identifying an end point, color information is propogated back “up” through the tree to the originally emitted rays, through the primitives intersected by satisfying the outstanding data requirements of each shader for those intersected primitives.
Matt Pharr, et al. in “Rendering Complex Scenes with Memory-Coherent Ray Tracing” Proceedings of SigGraph (1997) (“Pharr” herein) discloses aspects of a way, and its applicability in certain ray tracing situations, to avoid recursing up a tree of rays to determine a contribution by a ray to a pixel. Pharr discloses a decomposition of the computation for the outgoing radiance at a point into a sum of incoming radiances, and Pharr states that such decomposition allows rays to be processed independently from each other, with some limitations. Pharr attributes the concept of such decomposition to Cleary J. M., et al, “Multiprocessor Ray Tracing” Computer Graphics Forum 5(1):3-12, March 1986 (“Cleary”).
Cleary proposes subdividing a 3-D scene into a plurality of cubes, assigning tracing rays in each cube to a processor, and linking each processor to each of its neighbors. Rays are emitted into the scene from one face of the cube (where the face is subdivided into pixels representing screen pixels), and results of local ray shading computations are passed back through links to the face for use in determining colors of pixels at the face.